/*
 * @lc app=leetcode.cn id=142 lang=javascript
 *
 * [142] 环形链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 var detectCycle = function(head) {
    const map = new Map();
    while(head !== null) {
        if(map.has(head)) {
            return head;
        }
        map.set(head,1);
        head = head.next;
    }
    return null;
};

var detectCycle1 = function(head) {
    let slow = head;
    let fast = head;
    while(fast !== null) {
        slow = slow.next;
        if(fast.next !== null) {
            fast = fast.next.next;
        } else {
            return null;
        }
        if(fast === slow) {
            let p = head;
            while(p !== slow) {
                p = p.next;
                slow = slow.next;
            }
            return p;
        }
    }
    return null;
};
// @lc code=end

